package com.work.zhuanti.backtrack;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * title : 分割回文串
 * solution : 回溯法
 * link : https://leetcode-cn.com/problems/palindrome-partitioning/
 * Created by suk on 2020/9/7.
 */
public class T131_Partition_01 {

    public static void main(String[] args) {
        T131_Partition_01 t = new T131_Partition_01();
        String s = "abcca";
        System.out.println(t.partition(s));
    }

    LinkedList<String> track = new LinkedList<>();
    List<List<String>> res = new ArrayList<>();

    public List<List<String>> partition(String s) {
        backtrack(s, 0);
        return res;
    }

    public void backtrack(String s, int i) {
        int len = s.length();
        if (i == len) {
            res.add(new LinkedList<>(track));
            return;
        }

        for (int j = i; j < len; j++) {
            // 判断子串是否为回文,进行剪枝操作
            if (!judge(s.substring(i, j + 1)))
                continue;
            track.add(s.substring(i, j + 1));
            backtrack(s, j + 1);
            track.removeLast();
        }

    }

    // 判断是否是回文
    public boolean judge(String s) {
        StringBuilder sb = new StringBuilder(s);
        String reverse = sb.reverse().toString();
        return s.equals(reverse);
    }

}
